/*
 * @: 堆
 * @version: 1.0
 * @Author: ziwei
 * @Date: 2022-01-08 17:20:45
 * @LastEditors: ziwei
 * @LastEditTime: 2022-01-09 22:39:07
 */

class Heap{
 constructor(data=[]){
     this.data = data
     this.heapify();
 }
 size(){
     //返回数组大小
     return this.data.length
 }
 //创建时堆数据调整
 heapify(){
     if(this.size<2) return
     for(let i=1;i<this.data.length;i++){
         this.bubbleUp(i);
     }
 }
 //尾部插入元素
 offer(val){
     this.data.push(val)
     this.bubbleUp(this.size()-1);
 }
 //头部弹出
 poll(){
     if(!this.size()) return null;
     const res = this.data[0];//旧的头元素
     this.data[0]=this.data.pop();//将尾部元素，放到头的位置
     if(this.size()){
         this.bubbleDown(0);//向下调整
     }
     return res;
 }
 swap(i,j){
     if(i==j) return
     [this.data[i],this.data[j]] = [this.data[j],this.data[i]]
 }
 //向上调整
 bubbleUp(index){
    while(index>0){
        let parentIndex = Math.floor((index-1)/2)
        if(this.data[index]>this.data[parentIndex]) break; 
        this.swap(index,parentIndex);
        index = parentIndex
    }
 }
 //向下调整
 bubbleDown(index){
     let lastIndex = this.size()-1
     while(index<lastIndex){
         let leftIndex = index*2+1
         let rightIndex = index*2+1

         let findIndex = index
         if(this.data[rightIndex]<this.data[findIndex]){
             findIndex = leftIndex
         }
         if(this.data[rightIndex]<this.data[findIndex]){
             findIndex = rightIndex
         }
         if(findIndex==index) break
         this.swap(index,findIndex)
         index=findIndex
     }
 }
}

//
const heap = new Heap([1,2,3,4,5])